package com.company.heap;

/**
 * Created by v on 16-12-8.
 */
public class SkewHeap<E extends Comparable<E>>{
    private Node<E> root;
    private int size;

    private static class Node<E extends Comparable<E>>{
        private E element;
        private Node<E> left;
        private Node<E> right;

        public Node(E element){
            this.element=element;
        }
    }

    public int getSize() {
        return size;
    }

    //添加一个元素
    public void add(E e){
        size++;
        root=merge1(root,new Node<E>(e));
    }

    //合并两个斜堆
    public void merge(SkewHeap<E> heap) {
        root=merge1(root,heap.root);
        size+=heap.size;
        heap.clear();
    }

    public void clear(){
        size=0;
        root=null;
    }

    private Node<E> merge1(Node<E> h1,Node<E> h2){
        if(h1==null){
            return h2;
        }
        if(h2==null){
            return h1;
        }

        if(h1.element.compareTo(h2.element)<0){
            return merge2(h1,h2);
        }else {
            return merge2(h2,h1);
        }
    }

    private Node<E> merge2(Node<E> h1,Node<E> h2){
        if(h1.left==null){
            h1.left=h2;
        }else {
            h1.right=merge1(h1.right,h2);
            swapChildren(h1);
        }
        return h1;
    }

    //交换一个结点的两个儿子
    private void swapChildren(Node<E> t){
        Node<E> temp=t.left;
        t.left=t.right;
        t.right=temp;
    }

    //查看堆顶元素
    public E peek(){
        return root.element;
    }

    //返回堆顶元素并把它从堆顶删除
    public E poll(){
        E element=root.element;
        root=merge1(root.left,root.right);
        size--;
        return element;
    }
}
